package algorithm.niuke;

public class C矩形区域不超过K的最大数值和 {
    /*
     * 给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。
     * 
     * 示例:
     * 
     * 输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2, 3]]
     * 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。 说明：
     * 
     * 矩阵内的矩形区域面积必须大于 0。 如果行数远大于列数，你将如何解答呢？
     */
    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] sum = new int[row + 2][col + 2];
            for (int i = 1; i <= row; i++) {
                for (int j = 1; j <= col; j++) {
                    sum[i][j] = sum[i - 1][j] + matrix[i-1][j-1];
                }
            }
            return 0;
        }
    }
}
